package middle;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给定一个 排序好 的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 *
 * 整数 a 比整数 b 更接近 x 需要满足：
 *
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 *
 * 链接：https://leetcode-cn.com/problems/find-k-closest-elements
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FindKClosestElements {
    /**
     * 看了下官方的解答：
     * 使用二分查找 + 双指针的方法
     * 二分查找 定位到x的索引位置。然后开始分成三个情况：
     * 1. x的值 <= 数组元素的第一个值  取前k个
     * 2. x的值 >= 数组元素的最后一个值 取后k个
     * 3. 其他情况： 那么我们需要的 k 个数字肯定在范围 [index-k, index+k] 里面
     * 这种情况就是开始 对左右指针进行范围的缩小
     * 如果 l指针比0小 或者减去index元素绝对值 <= r-index的绝对值,那么r--
     * 如果 r指针越界了，或者减去index元素绝对值 < l-index的绝对值, 那么 l++
     * */
    class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            List<Integer> result = Arrays.stream(arr).boxed().collect(Collectors.toList());
            if(x <= arr[0]){
                return result.subList(0,k);
            }else if(x >= arr[arr.length-1]){
                return result.subList(arr.length - k, arr.length);
            }else{
                int index = binarySearch(arr, x);
                int low = Math.max(0, index - k), high = Math.min(arr.length - 1, index + k);
                while (high - low > k - 1) {
                    if ((x - result.get(low)) <= (result.get(high) - x))
                        high--;
                    else
                        low++;
                }
                return result.subList(low, high + 1);
            }

        }

        /**
         * 二分查找返回索引
         * */
        int binarySearch(int arr[], int target){
            int l = 0;
            int r = arr.length;

            while (l < r){
                int mid = l + (r - l) / 2;
                if(target > arr[mid]){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            return l;
        }
    }
}
